package sysu.el.graph.tree.algor;

import sysu.el.array.BoolArray;
import sysu.el.array.ints.ArrQueueInt;
import sysu.el.audit.Max2Int;
import sysu.el.audit.MaxInt;
import sysu.el.audit.MaxIntDes;
import sysu.el.graph.undi.UndiGT;
import sysu.el.graph.undi.UndiGTAdjList;
import sysu.el.tuple.Tuple;

public class TreeDiameter {
	
	public Max2Int max2;
	public MaxInt max1;
	public ArrQueueInt queue;
	public int sum[];
	
	public BoolArray isVisited;
	
	// Reference
	public int w[][];
	public UndiGTAdjList adj;
	
	public TreeDiameter(int nodeNum, int [][] w){
		max2 = new Max2Int();
		max1 = new MaxInt();
		queue = new ArrQueueInt(nodeNum);
		sum = new int[nodeNum];
		this.w = w;
		
		this.isVisited = new BoolArray(nodeNum);
	}
	
	/**
	 * 
	 * @param g
	 * @return T.a: Diameter
	 * @return T.b: Center
	 */
	public static Tuple.TDbl<Integer, Integer> getGraphDiameter(UndiGT g){
		TreeDiameter td = new TreeDiameter(g.getNodeNum(), g.weight.w);
		MaxIntDes<Integer> dia = new MaxIntDes<Integer>();
		for (int a=0; a<g.getNodeNum(); a++){
			int c = td.calTreeDiameter(0, td.adj);
			dia.sample(c, a);
		}
		return new Tuple.TDbl<Integer, Integer>(dia.getAns(), dia.getDes());
	}
	
	
	// Enhance
	//-EL-TODO: Why UndiGTAdjList should be separate apart? Fuck! Maybe for different tree?
	public int calTreeDiameter(int root, UndiGTAdjList adj){
		this.adj = adj;
		max2.reset();
//		queue.reset();
		this.isVisited.reset();
		this.isVisited.setVisited(root);
		
		int rootChildren[] = this.adj.getList(root);
		for (int in=0; in<this.adj.getDegree(root); ++in){
			int starter = rootChildren[in];
			queue.reset();
			queue.add(starter);
			this.isVisited.setVisited(starter);
			sum[starter] = this.w[starter][root];
			max1.reset();
			
			while (queue.isNotEmpty()){
				int h = queue.forward();
				int i = adj.getDegree(h) - 1;
				if (i == 0){
					max1.sample(sum[h]);
					continue;
				}
				while (i >= 0){
					int node = adj.getList(h)[i];
					if (this.isVisited.isUnvisited(node)){
						queue.add(node);
						this.isVisited.setVisited(node);
						sum[node] = sum[h] + w[h][node];
					}
					-- i;
				}
			}
			
			max2.sample(max1.getAns());
		}
		
		if (max2.ans1 == Integer.MIN_VALUE)
			max2.ans1 = 0;
		if (max2.ans2 == Integer.MIN_VALUE)
			max2.ans2 = 0;
//		System.out.println(max2.ans1 + "\t" + max2.ans2);
		return max2.ans1 + max2.ans2;
	}
	

}
